def sumPos(a, b):
	return (int(a[0]+b[0]), int(a[1]+b[1]))
	
def subPos(a, b):
	return (int(a[0]-b[0]), int(a[1]-b[1]))

def multPos(c, pair):
	return (int(c*pair[0]), int(c*pair[1]))

def absPos(a):
	return (int(a[0]/abs(a[0])), int(a[1]/abs(a[1])))

class Game:
	boardWidth = 8
	boardHeight = 8
	def __init__(self):
		self.turn = 'O'
		self.validMoves = []
		self.createBoard()
		self.initializeBoard()
		
	def __getitem__(self, pos):
		return self.board[pos[0]][pos[1]]
	
	def isEmpty(self, pos):
		return self.insideBoard(pos) and self[pos] == ' '
		
	def insideBoard(self, pos):
		return pos[0]>=0 and pos[1]>=0 \
			and pos[0] < Game.boardWidth \
			and pos[1] < Game.boardHeight
			
	def changeTurn(self):
		if self.turn == 'O':
			self.turn = 'X'
		else:
			self.turn = 'O'
				
	def createBoard(self):
		self.board = []
		for i in range(Game.boardWidth):
			self.board.append([])
			for j in range(Game.boardHeight):
				self.board[i].append(' ')
				
	def initializeBoard(self):
		for j in range(0,3):
			for i in range(Game.boardWidth):
				if ((i+j)%2 != 0):
					self.board[i][j] = 'O'
		
		for j in range(5,Game.boardHeight):
			for i in range(Game.boardWidth):
				if ((i+j)%2 != 0):
					self.board[i][j] = 'X'
				
	def move(self, org, dst):
		# to do: check if this works
		if self.insideBoard(org) and dst in self.validMoves:
			hasEaten = False
			if self.canEat(org, dst):
				self.board[self.dead[0]][self.dead[1]] = ' '
				hasEaten = True

			if (dst[1] == 0 and self.turn == 'X') or (dst[1] == Game.boardHeight-1 and self.turn == 'O'):
				self.board[org[0]][org[1]] = self.board[org[0]][org[1]].lower()
				
			self.board[dst[0]][dst[1]] = self.board[org[0]][org[1]]
			self.board[org[0]][org[1]] = ' '

			if (not hasEaten) or (not self.posHasMandatoryMoves(dst)):
				self.changeTurn()
		self.validMoves = list()
		
	def canEat(self, org, dst):
		# TO DO: improve this...
		if self.isKing(org):
			diagonal = absPos(subPos(dst, org))
			mid = sumPos(org, diagonal)
			while self.isEmpty(mid) and mid != dst:
				mid = sumPos(mid, diagonal)
			if mid != dst and self.insideBoard(mid) and self[mid].upper() != self.turn:
				self.dead = mid
				return True
			else:
				return False
		else:
			mov = subPos(dst, org)
			if abs(mov[0])==1 or abs(mov[1])==1:
				return False
			mid = multPos(0.5, sumPos(org, dst))
			if (not self.isEmpty(mid)) and (self[mid].upper() != self.turn) and self.isEmpty(dst):
				self.dead = mid
				return True
			else:
				return False
		
	def isRetreating(self, pos, move):
		return (self.turn=='O' and pos[1]>move[1]) or (self.turn=='X' and pos[1]<move[1])
	
	def generateMoves(self, pos):
		if self.isKing(pos):
			self.generateKingMoves(pos)
		else:
			self.generateCommonMoves(pos)

	def generateEatingMoves(self, pos):
		neighborhood = [(1,1), (1,-1), (-1,-1), (-1,1)]
		moves = []
		for neighbor in neighborhood:
			dst = sumPos(pos,multPos(2,neighbor))
			if self.isEmpty(dst) and self.canEat(pos, dst):
				moves.append(dst)

		return moves

	def hasMandatoryMoves(self):
		for j in range(Game.boardHeight):
			for i in range(Game.boardWidth):
				if self.board[i][j].upper() == self.turn:
					if (len(self.generateEatingMoves((i,j))) > 0) or (self.isKing((i,j)) and len(self.generateKingEatingMoves((i,j))) > 0):
						return True
		return False

	def posHasMandatoryMoves(self, pos):
		if self[pos].upper() == self.turn:
			if (len(self.generateEatingMoves(pos)) > 0) or (self.isKing(pos) and len(self.generateKingEatingMoves(pos)) > 0):
				return True
		return False


	def isKing(self, pos):
		return self[pos] == 'o' or self[pos] == 'x'
		
	def generateCommonMoves(self, pos):
		neighborhood = [(1,1), (1,-1), (-1,-1), (-1,1)]
		hasToEat = self.hasMandatoryMoves()
		self.validMoves = []
	
		eatingMoves = self.generateEatingMoves(pos)
		self.validMoves += eatingMoves
		for neighbor in neighborhood:
			dst = sumPos(pos,neighbor)
			if (not hasToEat) and self.isEmpty(dst) and (not self.isRetreating(pos, dst)):
				self.validMoves.append(dst)

	def generateKingMoves(self, pos):
		neighborhood = [(1,1), (1,-1), (-1,-1), (-1,1)]
		hasToEat = self.hasMandatoryMoves()
		self.validMoves = []

		self.validMoves += self.generateKingEatingMoves(pos)
		for neighbor in neighborhood:
			dst = sumPos(pos, neighbor)
			while self.isEmpty(dst):
				if not hasToEat:
					self.validMoves.append(dst)
				dst = sumPos(dst, neighbor)

	def generateKingEatingMoves(self, pos):
		neighborhood = [(1,1), (1,-1), (-1,-1), (-1,1)]
		moves = []
		for neighbor in neighborhood:
			dst = sumPos(pos, neighbor)
			while self.isEmpty(dst):
				dst = sumPos(dst, neighbor)
			if self.insideBoard(dst) and self[dst].upper() != self.turn:
				dst = sumPos(dst, neighbor)
				while self.isEmpty(dst):
					moves.append(dst)
					dst = sumPos(dst, neighbor)

		return moves
